/**
 * @author ：FeatherWaves
 * @description：TODO
 * @date ：2021/8/26 10:10
 */


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
class Partition {
    private ListNode buyNode(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = null;
        return newNode;
    }
    public void addLast(ListNode pHead, int val) {
        ListNode newNode = buyNode(val);
        if (null == pHead) {
            pHead = newNode;
        } else {
            ListNode cur = pHead;
            while (null != cur.next) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
    }
    public void partition(ListNode pHead, int x) {
        // write code here
        if (null == pHead) {
            return;
        } else {
            ListNode l1 = null;
            ListNode l2 = null;
            ListNode cur = pHead;

            while (null != cur) {
                if (x <= cur.val) {
                    addLast(l1, cur.val);
                } else {
                    addLast(l2, cur.val);
                }
                cur = cur.next;
            }
            cur = l1;
            while (null != cur.next) {
                cur = cur.next;
            }
            cur.next = l2;
        }
    }
}

public class Solution {
    public static void main(String[] args) {
        Partition ll = new Partition();
        ListNode pHead = null;
        ll.addLast(pHead, 12);
        ll.addLast(pHead, 8);
        ll.addLast(pHead, 13);
        ll.addLast(pHead, 5);
        ll.addLast(pHead, 2);
        ll.partition(pHead, 12);

    }
}
